KURZUS: Alkalmazott operációkutatás

MODUL: II. modul: Egészértékű programozási feladat fogalma és grafikus megoldása. Néhány nevezetes egészértékű modell

6. lecke: Az egészértékű programozási feladatok fogalma és megoldási módszerei

|  | Tanulási útmutató
| Az egészértékű programozási feladatok fogalma és megoldási módszerei a tankönyv 5. fejezetében találja meg. Néhány nevezetes egészértékű modell nevét, fogalmát és matematikai modelljét a tankönyv 5.6. fejezetében találja meg.
| Az egészértékű programozási modellek ugyancsak megoldhatók a Solver programmal. Ez teljesen megegyezik a 4. leckében megismert eljárással. Egészértékű feladatok jellegzetessége, hogy megköveteljük, bizonyos változók csak egész értéket vehetnek fel. Ezt a Solver programban beállíthatjuk. A "Korlátozó feltételek" mező mellett a "Hozzáadás" gombra kattintunk (lásd 1. ábra!).
1. ábra
| A megjelenő párbeszédablak lenyíló menüjéből választható ki az "int" lehetőség (2. ábra!).
2. ábra
| Az int (integer = egész) jelenti az egészértékűséget, bin (bináris) jelenti azt, hogy a változó csak a 0 vagy 1 értékét veheti fel.
| Tevékenységek
| Figyelmesen olvassa el az egészértékű lineáris programozási feladat definícióját, és jól jegyezze meg a matematikai modelljét.
| Rögzítse szemével a tankönyvben található ábra segítségével az egészértékűség megoldási problémáinak nehézségét!
| Tanulmányozza a probléma lényegéből adódó speciális matematikai eljárásokat.
| A Gomory-féle módszer lényegét jól végigkövetheti a tankönyvben található példán. Nem kell a számításokat végigvinni, mert a Solver program itt is nagy segítségünkre van.
| A tankönyvben található feladatot oldja meg a Solver segítségével! Vigyázzon arra, hogy a feltételek Hozzáadásánál a bal oldalon jelölje ki a változók tartományát, középen jelölje be int és jobb oldalon újból a változók tartományát. Ha nem tiszta egészértékű a feladat, akkor csak a szóban forgó változók celláira tegye meg ezt. Ha a változó csak 0 vagy 1 értéket vehet fel, akkor a bin lehetőséget jelölje ki.
| Tanulmányozza át a tankönyvben található egészértékű modelleket. Különösen jól jegyezze meg a Hátizsák- és a Hajórakodási problémát. Mindenképpen jegyezze meg a modellben szereplő jelölések matematikai és gazdasági jelentését.
| Követelmények
| Felsorolásból ki tudja választani az egészértékű programozási feladatok definícióját és a megoldási eljárások lényegét. Adott egészértékű feladatot Solver segítségével meg tudjon oldani. Kétváltozós egészértékű feladatot grafikusan meg tudjon oldani.

|  | Bemutató feladat
| Egy gépeket gyártó vállalkozás háromféle terméket tud gyártani. A termeléshez három erőforrás áll rendelkezésre, amelyek a termelés kapacitását korlátozzák. Az erőforrások kapacitása és a termékek fajlagos erőforrás szükségletét a táblázat tartalmazza:
| I. | II. | III. | Kapacitás
E1 | 1 | 2 | 1 | 10
E2 | 1 | -1 | 1 | 8
E3 | 0 | 1 | 1 | 2
| A nyereség együtthatók: 3, 1, 1 A cég a harmadik erőforrást teljes mértékben ki akarja használni, és a nyereséget maximalizálni szeretné. Határozza meg a termékösszetételt Solver segítségével. A termékek jellegéből adódóan az egyes termékek mennyiségére csak egész értékű megoldás lehet.
| Vigyük be az adatokat Excelbe, és a már tanult módon töltsük ki a cellákat!
| Nyissuk meg a Solvert, és az alábbi módon írjuk be a korlátozó feltételeket:
| Korlátozó feltételek: egyenként kell felvenni őket:
| $B$7:$D$7=egész érték $E$3<=$G$3 $E$4<=$G$4 $E$5=$G$35
| Ezután kattintsunk a megoldás gombra:

|  | Önellenőrző feladatok
| 1. Válassza ki a helyes állítást!
| "Egészértékű lineáris programozási feladatnak nevezzük azt a modellt, ahol..."
| a változók csak valós számok lehetnek.
| a modellben szereplő számok egész számok.
| kikötjük, hogy a változói csak nemnegatív egész értéket vehetnek fel.
| a jobb oldalon csak egész szám szerepel.
| 2. Oldja meg Solver program segítségével az alábbi lineáris programozási feladatot!
| a) x 1 , x 2 , x 3 , ≥ 0 5 x 1 +3 x 2 − x 3 ≤ 27 3 x 1 +2 x 2 +4 x 3 ≥ 25 2 x 1 + x 2 + x 3 = 10 z=90 x 1 +50 x 2 +30 x 3 → max⁡
| Írja be a megfelelő helyre az optimális megoldás értékeit! x 1 = x 2 = x 3 = z =
| b) Oldja meg a feladatot úgy, hogy az x 2 , x 3 változó értéke csak egész lehet.
| Írja be a megfelelő helyre a kapott értékeket! x 1 = x 2 = x 3 = z =
| 3. Oldja meg grafikusan az alábbi kétváltozós tiszta egészértékű feladatot.
| x 1 , x 2 ≥ 0 x 1 +2 x 2 ≤ 8 x 1 + x 2 ≤ 5 x 1 ≥ 1 2 x 1 ≤ 7 z=20 x 1 +10 x 2 → max⁡
| Vegyen elő egy négyzetrácsos lapot, ábrázolja grafikusan a megadott feltételi egyenlőtlenségeket. Jelölje ki a lehetséges megoldások halmazát!
| a) Adja meg a lehetséges megoldások halmazának csúcspontjait! Kezdje az x1 tengelyen lévő, az origóhoz legközelebbivel és az óramutató járásával ellenkező irányban folytassa. Ha egy koordináta nem egész számra jön ki, akkor kerekítse 0,5-re. Például az 1 és 2 közötti érték esetén 1,5-et írjon. A(;), B(;), C(; ), D(;), E(;)
| b) Írja be az optimális megoldást a megfelelő helyre, ha létezik! x 1 = x 2 = z e g y ü t t =